package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//在选举中，第 i 张票是在时间为 times[i] 时投给 persons[i] 的。 
//
// 现在，我们想要实现下面的查询函数： TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。 
//
// 在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。 
//
// 示例： 
//
// 输入：["TopVotedCandidate","q","q","q","q","q","q"],
// [
//  [
//      [0,1,1, 0, 0, 1, 0],
//      [0,5,10,15,20,25,30]
//  ],
//  [3],[12],[25],[15],[24],[8]
// ]
//输出：[null,0,1,1,0,0,1]
//解释：
//时间为 3，票数分布情况是 [0]，编号为 0 的候选人领先。
//时间为 12，票数分布情况是 [0,1,1]，编号为 1 的候选人领先。
//时间为 25，票数分布情况是 [0,1,1,0,0,1]，编号为 1 的候选人领先（因为最近的投票结果是平局）。
//在时间 15、24 和 8 处继续执行 3 个查询。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= persons.length = times.length <= 5000 
// 0 <= persons[i] <= persons.length 
// times 是严格递增的数组，所有元素都在 [0, 10^9] 范围中。 
// 每个测试用例最多调用 10000 次 TopVotedCandidate.q。 
// TopVotedCandidate.q(int t) 被调用时总是满足 t >= times[0]。 
// 
// Related Topics 二分查找 
// 👍 37 👎 0


import java.util.HashMap;
import java.util.Map;

public class OnlineElection{
    public static void main(String[] args) {
        TopVotedCandidate solution = new OnlineElection().new TopVotedCandidate(new int[]{0,1,1, 0, 0, 1, 0}, new int[]{0,5,10,15,20,25,30});
        System.out.println(solution.q(3));
        System.out.println(solution.q(12));
        System.out.println(solution.q(25));
        System.out.println(solution.q(15));
        System.out.println(solution.q(24));
        System.out.println(solution.q(8));

        /*TopVotedCandidate solution = new OnlineElection().new TopVotedCandidate(new int[]{0,0,0,0,1}, new int[]{0,6,39,52,75});
        System.out.println(solution.q(45));
        System.out.println(solution.q(49));
        System.out.println(solution.q(59));
        System.out.println(solution.q(68));
        System.out.println(solution.q(42));
        System.out.println(solution.q(37));
        System.out.println(solution.q(99));
        System.out.println(solution.q(26));
        System.out.println(solution.q(78));
        System.out.println(solution.q(43));*/
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class TopVotedCandidate {

        private int[] persons;
        private int[] times;

        private int[] curPerson;

        public TopVotedCandidate(int[] persons, int[] times) {
            this.persons = persons;
            this.times = times;
            curPerson = new int[persons.length];
            builtCurPerson();
        }

        public int q(int t) {
            int l = 0, r = persons.length - 1;
            int m = -1;
            while(l + 1 < r){
                m = ((r - l) >> 1) + l;
                if(times[m] < t){
                    l = m;
                }else{
                    r = m;
                }
            }
            if(times[r] <= t) return curPerson[r];
            else return curPerson[l];
        }

        private void builtCurPerson(){
            Map<Integer, Integer> map = new HashMap<>(); // key:value => person[i] : count
            int max = -1, maxPerson = -1;
            int tmp = -1;
            for(int i = 0; i < persons.length; i ++){
                tmp = map.getOrDefault(persons[i], 0) + 1;
                map.put(persons[i], tmp);
                if(maxPerson == -1 || max <= tmp){
                    maxPerson = i;
                }
                max = Math.max(max, tmp);
                curPerson[i] = persons[maxPerson];
            }
            //System.out.println(map);
        }
    }

    /**
     * Your TopVotedCandidate object will be instantiated and called as such:
     * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
     * int param_1 = obj.q(t);
     */
    //leetcode submit region end(Prohibit modification and deletion)

}
